% \section{Implementação}
% 
% O planejamento da implementação foi realizado sobre a biblioteca criptográfica
% Relic~\cite{relic-toolkit}. Para uma implementação completa do teste, é
% necessário uma ferramenta que forneça aritmética multi-precisão, suporte à
% manipulação de números inteiros muito grandes que extrapolariam a precisão de
% qualquer tipo primitivo de variáveis.
% 
% Em resolução com a Relic, a implementação foi executada utilizando a linguagem C
% padrão C99. Antes da implementação do teste em si, foi necessário elaborar
% funções específicas de utilidade comum e de operações em anel polinomial que não eram
% cobertas pela biblioteca. As principais delas serão discutidas nos tópicos a
% seguir.
% 
% \subsection{Quadrado Perfeito}
% 
% A raiz quadrada de um inteiro $a$ com $n$ \emph{bits} deve estar contida no
% intervalo $(\; 2^{\lfloor \frac{n-1}{2} \rfloor}, \;2^{\lfloor \frac{n}{2}
% \rfloor})$. É possível, de forma semelhante a uma busca binária, encontrar a
% raiz inteira de $a$ com o custo de $O($log$_2\: n)$ multiplicações.
% 
% Tendo a raiz inteira $c$ de $a$, basta verificar se $c^2 = a$ para determinar se
% $a$ é quadrado perfeito.
% 
% 
% \subsection{Aritmética Básica}
% \label{basic-arit}
% 
% Adição e subtração de polinômios de mesmo grau é feita de maneira natural,
% respeitando a ordem de cada coeficiente e a redução módulo $n$.
% 
% A multiplicação de dois polinômios de graus $m$ e $n$, resulta em um
% polinômio de grau $m+n$. Como a aritmética do teste é realizada no grupo
% multiplicativo $R(c, n)^*$, módulo $\mathbb{Z}_n$ e o polinômio quadrático $x^2
% - c$, pode-se chegar a uma fórmula fechada para a multiplicação e redução:
% $(a_1b_0 + a_0b_1)x + a_0b_0 + a_1b_1c$.
% 
% 
% O custo de processamento desses algoritmos é limitado pelo número de
% multiplicações, quadrados e reduções entre números grandes, portanto iremos
% desconsiderar o custo das somas e subtrações, que em geral são desprezíveis.
% Deste modo, uma multiplicação de dois polinômios tem o custo de quatro
% multiplicações e uma redução de coeficientes em $\mathbb{Z}_n$.
% 
% Para o quadrado de um polinômio em $R(n,c)^*$, basta usar o mesmo
% resultado de anterior para $a = b$, que resulta em $a^2 = 2a_1a_0x + a_0^2 +
% a_1^2c$ com o custo de uma multiplicação e dois quadrados.
% 
% 
% \subsection{Exponenciação Modular}
% 
% A maneira mais ingênua, até mesmo para números de precisão simples, de calcular
% $c = a^k$ mod $n$ consiste em realizar $k-1$ multiplicações. Em aplicações
% criptográficas, a grandeza de $k$ normalmente excede $2^{512}$ ou $2^{1024}$.
% Computar tais multiplicações tomaria mais tempo do que a vida do Universo, o
% que torna ineficaz tal abordagem.
% Podemos descrever a exponenciação na seguinte forma recursiva:
% 
% \begin{align*}
% a^k =
% \begin{cases}
% 1 & \text{se } k = 0 \\
% a\cdot \Big(a^{\frac{k-1}{2}}\Big)^2 & \text{se } k \equiv 1
% \text{ (mod $2$)}\\
% \Big(a^{\frac{k}{2}}\Big)^2 & \text{se } k \equiv 0 \text{ (mod $2$)}
% \end{cases}
% \end{align*}
% 
% Utilizando essa ideia, podemos entender as sucessivas divisões por $2$ como um
% \emph{shift right} nos \emph{bits} do expoente. O algoritmo implementado é o de
% exponenciação modular esquerda para direita, neste caso, a exponenciação modular
% é realizada com $O($log$_2\;n)$ quadrados e $o($log$_2\;n)$ multiplicações.


\section{Implementation} 

The implementation planning was performed over the Relic cryptographic
library~\cite{relic-toolkit}. For a complete implementation of the test, is
necessary a tool that provides multi-precision arithmetics, support manipulation
of very large integers with precisions that would extrapolate any primitive
type variables.

In resolution with Relic, the implementation was executed using the C
language in C99 standard. Before the implementation of the test itself, it was
necessary to develop specific common utility functions and operations over
polynomial ring that were not covered by the library. The major of them will be
discussed in the following topics.

\subsection{Perfect Square}

The square root of an integer $a$ with $n$ bits must be bounded by 
$(\;2^{\lfloor \frac{n-1}{2} \rfloor}, \;2^{\lfloor \frac{n}{2}
\rfloor})$. It is possible, similar to a binary search, to find 
the integer root of $a$ with the cost of $O($log$ _2 \:n)$ multiplications. 

Holding the integer root $c$ of $a$, just need to check if $c^2 = a$ to
determine whether $a$ is a perfect square or not. 

\subsection{Basic Arithmetics} 
\label{basic-arit}

Same degree polynomials addition and subtraction are taken in a natural way,
respecting the order of each coefficient and reduction modulo $n$.

The multiplication of two polynomials with degree $ m $ and $ n $, results in a 
polynomial of degree $m + n$. As the arithmetic test is performed in the 
multiplicative group $R(c, n)^*$, modulo $\mathbb{Z}_n$ and the quadratic
polynomial $x^2-c$, one can reach a closed formula for multiplication and reduction:
$(a_1b_0 a_0b_1 +) x + + a_0b_0 a_1b_1c$. 


The processing cost of these algorithms is limited by the number of 
multiplications, squares and reductions between large numbers, so we will 
disregard the cost of additions and subtractions, which are generally negligible. 
Thus, a multiplication of two polynomials has the cost of four 
multiplications and a coefficients reduction in $\mathbb{Z}_n $. 

To square a polynomial in $R(n, c)^*$, just use the same 
previous result for $a = b$, following in $a^2 = 2a_1a_0x + a_0^2 + 
a_1^2c$ with the cost of one multiplication and two squares.

\subsection{Modular Exponentiation} 

The most naive way, even for single-precision numbers, for calculating 
$c = a^k$ mod $n$ would be to make $k-1$ multiplications. in 
cryptographic applications, the size of $k$ usually exceeds $2^{512}$ or
$2^{1024}$.
Computing such multiplications would take longer than the Universe lifetime, a
prohibitive approach.
Exponentiation can be described in the following recursive form:

\begin{align*}
a^k =
\begin{cases}
1 & \text{if } k = 0 \\
a\cdot \Big(a^{\frac{k-1}{2}}\Big)^2 & \text{if } k \equiv 1
\text{ (mod $2$)}\\
\Big(a^{\frac{k}{2}}\Big)^2 & \text{if } k \equiv 0 \text{ (mod $2$)}
\end{cases}
\end{align*}

Using this idea, the consecutive divisions by $2$ can be seen as a 
shift right operation in exponent bits. The implemented algorithm is the
Left-to-right binary exponentiation, in this case, the modular exponentiation 
is performed with $O($log$_2\;n)$ squares and $o($log$_2\;n)$ multiplications.
